# 字节面试题： 
"""
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的整数，并返回他们的数组。
你可以假设每种输入只会对应的答案，不能重复利用这个数组中同样的元素。
示例:
给定 nums = [1，2, 3, 4,11, 15], target = 16
[1,15]   [2,3,11]   [1,4,11]
"""
# 组合总数(和这题很像，似乎难度还要小一些) : https://leetcode-cn.com/problems/combination-sum/



# 方法1，使用集合类型 加 元组去重（要排序， 元素相同，顺序不同也属于不同元组）
class Solution1:
    def combinationSum(self, candidates: list, target: int) -> list:
        """
            因为元素可以重复使用，基本上就是全排列了。 每次都可以选择 数组中的任意一个
        """
        rst = set()
        def gTargetList(nums, total):
            if total == target:
                # 大坑..... 不能连着写成 t = nums[:].sort()  这相当于是接收sort() 函数的返回值了
                t = nums[:]
                t.sort()
                rst.add(tuple(t))
                return 

            for num in candidates:
                if num not in nums:
                    nums.append(num)
                    gTargetList(nums, total + num)
                    nums.pop()

        gTargetList([], 0)
        return list(rst)


# 方法二：直接用 in 操作符，判断排序后的数组是否在结果列表里面
class Solution:
    def combinationSum(self, candidates: list, target: int) -> list:
        """
            因为元素可以重复使用，基本上就是全排列了。 每次都可以选择 数组中的任意一个
        """
        rst = list()
        def gTargetList(nums, total):
            if total == target:
                # 大坑..... 不能连着写成 t = nums[:].sort()  这相当于是接收sort() 函数的返回值了
                t = nums[:]
                t.sort()
                if t not in rst:
                    rst.append(t)
                return 
            elif total > target:
                return 

            for num in candidates:
                if num not in nums:
                    nums.append(num)
                    gTargetList(nums, total + num)
                    nums.pop()

        gTargetList([], 0)
        return list(rst)


# 方法三：

nums = [1, 2, 3, 4, 11, 15]
target = 16 

s = Solution()
rst = s.combinationSum(nums, 16)
print(rst)
